package com.ly.algorithm.leetcode.linked;

/**
 * @Classname Problem344
 * @Description
 *
 *将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 *
 * 示例：
 *
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 *
 *
 *
 * @Date 2020/12/14 20:59
 * @Author 冷心影翼
 */
public class Problem21 {

	public static void main(String[] args) {
		Solution21 solution21 = new Solution21();
		ListNode listNode1 = new ListNode(1);
		listNode1.next = new ListNode(2);
		listNode1.next.next = new ListNode(4);
		ListNode listNode2 = new ListNode(1);
		listNode2.next = new ListNode(3);
		listNode2.next.next = new ListNode(4);
		listNode2.next.next.next = new ListNode(5);
		listNode2.next.next.next.next = new ListNode(6);
		ListNode res = solution21.mergeTwoLists(listNode1, listNode2);
		res.printRes();
	}

}



class Solution21 {

	//输入：1->2->4, 1->3->4
	//输出：1->1->2->3->4->4
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode head = new ListNode(-1);
		ListNode pre = head;
		while (l1!=null && l2!=null) {
			if(l1.val<=l2.val) {
				pre.next = l1;
				l1 = l1.next;
			}else {
				pre.next = l2;
				l2 = l2.next;
			}
			pre = pre.next;
		}
		pre.next = l1==null?l2:l1;
		return head.next;
	}
}